package zuosheng.string;

/**
 * @author lj
 * @Description:
 * @date 2020-11-17 12:27
 * @QQ 851477108
 */


public class Manacher {
    public static void main(String[] args) {
        String str1 = "abc1234321ab";
        System.out.println(maxLcpsLength(str1));
    }

    //最大回文字符串长度
    public static int maxLcpsLength(String str){
        if (str == null || str.length() == 0){
            return 0;
        }

        char[] charArr = manacherString(str);

        //建立一个回文半径数组，pArr每个位置的最大回文半径值
        int[] pArr = new int[charArr.length];
        //遍历过所有字符中向右扩出来的最大右边界，初始回文半径数组（右侧）起始在-1位置
        int pR = -1;
        //更新pR,回文中心位置，字符数组初始为第一个#，位置为-1
        int index = -1;

        int max = Integer.MIN_VALUE;
        //具体流程
        //获得回文字符串长度数组最大值，整个过程分为回文半径在当前位置之前和之后两种情况，
        //其中回文半径在当前位置之后分为三种情况：当前位置对称位置的边界在左边界之前，之后，压线
        for (int i = 0; i != charArr.length; i++){
            //i的对称位置的回文和i到pR的距离，哪个小哪个作为起始距离，pR>i表示i在回文里面（之前）
            pArr[i] = pR > i ? Math.min(pArr[2 * index - i], pR - i) : 1;
            //条件为当前位置的半径不超出数组长度并且左边区域也没越界
            while (i + pArr[i] < charArr.length && i - pArr[i] > -1){
                //扩位置（当前位置对称位置的边界在左边界之前，之后不需要要扩，直接break）
                if (charArr[i + pArr[i]] == charArr[i - pArr[i]]){
                    pArr[i]++;
                }else {
                    break;
                }
            }
            //确定回文半径右边界
            if (i + pArr[i] > pR){
                pR = i + pArr[i];
                index = i;
            }

            max = Math.max(max, pArr[i]);
        }
        return max - 1;
    }

    //将str进行处理,把每个字符开头、结尾和中间插入一个#得到一个新字符串数组
    //将字符串的前后以及中间都加#字符，变为字符数组
    public static char[] manacherString(String s){
        char[] charArr = s.toCharArray();
        char[] res = new char[s.length() * 2 + 1];
        int index = 0;
        for (int i = 0; i != res.length; i++){
            //判断奇偶,如果(i & 1) == 0 ture,则i为奇数
            res[i] = (i & 1) == 0 ? '#' : charArr[index++];
        }
        return res;
    }
}
